package com.剑指offer.第四章;

public class 链表中环的入口节点 {

    /**
     * 获取环中的一个节点 使用两个指针 同时从链表中的头节点出发
     * 一个指针走一次 另一个指针走两次 当第二个指针等于第一个指针时说明 存在环形链表 并且返回这个节点。
     *
     * @return
     */
    public static ListNode getNodeInLoop(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode slow = head;

        ListNode fast = slow.next;

        while (slow != null && fast != null) {
            if (slow == fast) {
                return slow;
            }
            slow = slow.next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }
        }
        return null;
    }

    /**
     * 需要直到环中节点数的解法
     * 拿到环中的一个节点node时，可以循环next，没循环一次加1 直到next=node可以退出循环
     *
     * @return
     */
    public static ListNode resolve(ListNode head) {
        ListNode nodeInLoop = getNodeInLoop(head);
        if (nodeInLoop == null) {
            return nodeInLoop;
        }

        /**
         * 获取环中节点
         */
        int count = 1;
        for (ListNode n = nodeInLoop.next; n != nodeInLoop; n = n.next) {
            count++;
        }

        /**
         * 先让第一个指针移动count步数
         */
        ListNode fast = head;
        for (int i = 0; i < count; i++) {
            fast = fast.next;
        }

        ListNode slow = head;

        /**
         * 相等则说明是入口节点
         */
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode p1 = new ListNode(1);
        ListNode p2 = new ListNode(2);
        ListNode p3 = new ListNode(3);
        ListNode p4 = new ListNode(4);
        ListNode p5 = new ListNode(5);
        head.next = p1;
        p1.next = p2;
        p2.next = p3;
        p3.next = p4;
        p4.next = p5;
        p5.next = p3;

        ListNode resolve = resolve(head);
        System.out.println(resolve.val);
    }

}
